package com.mystudy.dataStructure.collections;


/**
 * @program: infoalgorithm
 * @description: 基于链表的映射
 * @author: zhouzhilong
 * @create: 2019-07-29 14:33
 **/
public class LinkedListMap<K, V> implements Map<K, V> {
    private Node dummyHead;
    private int size;

    public LinkedListMap() {
        this.dummyHead = new Node();
        this.size = 0;
    }

    @Override
    public void add(K key, V val) {
        //不允许两个节点具有同样的key，所以要先遍历
        Node result = getNode(key);
        if (result == null) {
            dummyHead.next = new Node(key, val, dummyHead.next);
            size++;
        } else {
            //此时已经存在了key代表的值，所以认为这里是想要更新数据
            result.val = val;
        }
    }

    private Node getNode(K key) {
        Node cur = dummyHead.next;
        while (cur != null) {
            if (cur.key == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }


    @Override
    public V remove(K key) {
        Node prev = dummyHead;
        while (prev.next != null) {
            Node cur = prev.next;
            if (cur.key == key) {
                prev.next = cur.next;
                cur.next = null;
                size--;
                return cur.val;
            }
            prev = prev.next;
        }
        return null;
    }

    @Override
    public boolean contains(K key) {
        return getNode(key) != null;
    }

    @Override
    public V get(K key) {
        Node result = getNode(key);
        return result == null ? null : result.val;
    }

    @Override
    public void set(K key, V val) {
        Node result = getNode(key);
        if (result == null) {
            throw new IllegalArgumentException(key + "doesn't exist!");
        }
        result.val = val;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }


    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
       Node cur = dummyHead.next;

        while (cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL");
        return res.toString();
    }

    private class Node {
        public K key;
        public V val;
        public Node next;

        public Node(K key, V val, Node next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }

        public Node(K key) {
            this(key, null, null);
        }

        public Node() {
            this(null, null, null);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", val=" + val +
                    '}';
        }
    }
}
